# -*- coding: utf-8 -*-

'''
@author: Luis Fonte n6043
@date: 06/10/2013
@obs: Code created on class from documentation given by teacher
'''

import math


class Heapsort:
  '''
  Class Heapsort
  Class with a heap sort algorithm implemented on function heapSort
  '''

  
  def __init__(self, A):
    '''
    Constructor of class
    @param A - list with numbers desordered
    '''
    self.A = A #list passed by parameter
    self.heapsize = len(A) 
    pass

  
  def left(self, i):
    '''
    left function
    Sets left node
    @param i - node i
    '''
    return (2*i)
    pass

  
  def right(self, i):
    '''
    left function
    Sets right node
    @param i - node i
    '''
    return (2*i) + 1
    pass

  
  def parent(i):
    '''
    parent function
    Sets Parent node
    @param i - node i
    '''
    return int (math.floor((i-1)/2.0))
    pass

  
  def maxHeapify(self, i):
    '''
    maxHeapify Function
    the value given to the node is equal to parent node, in the best situation
    @param i - node i
    '''
    l = self.left(i)
    r = self.right(i)
    largest = 0
    if l < self.heapsize and self.A[l] > self.A[i]:
      largest = l
    else: largest = i
    if r < self.heapsize and self.A[r] > self.A[largest]:
      largest = r
    if largest != i:
      self.A[i], self.A[largest] = self.A[largest], self.A[i]
      self.maxHeapify(largest)
    pass

  
  def buildMaxHeap(self):
    '''
    buildMaxHeap Function
    builds a heap from a list
    '''
    self.heapsize = len(self.A)
    for i in range (len(self.A)/2, 0, -1):
      self.maxHeapify(i)
      pass
    pass

  
  def sort(self):
    '''
    sort Function
    Algorithm Heap Sort
    list ordination is given by right position of the elements from the top of the heap
    '''
    self.buildMaxHeap()
    for i in range(len(self.A)-1, 0,-1):
      temp = self.A[i]
      self.A[i] = self.A[0]
      self.A[0] = temp
      self.heapsize = self.heapsize - 1
      self.maxHeapify(0)
    pass

  pass
